1. Field of Invention
A method for managing the spare blocks of an optical disc, more particularly one based on using the spare block address to access the spare block usage status.
2. Description of the Prior Art
Because an optical disc is inexpensive, compact, light in weight, and can store a huge amount of data, optical discs are becoming the most frequently used data storage media in the modern information society. With the introduction of a writable optical disc allowing each user to write his or her own data onto the optical disc to meet personal needs, the optical disc is becoming one of the most important portable personal storage media. How to access data on the writable optical disc more reliably and more efficiently is now a focal point of research in the modern information industry.
An optical disc drive is necessary to access data on the optical disc. Please refer to FIG. 1. FIG. 1 is a functional block diagram of a typical optical disc drive 10 that is used to access an optical disc 22. There is a loader 14 to hold the optical disc 22 in the optical disc drive 10, one motor 12 that spins the loader 14, a control circuit 18 that controls operation of the optical disc drive 10, and a memory 20 (such as a volatile random access memory) to temporarily hold the data needed by the controlling circuit 18 during an operational period. The optical disc 22 has tracks 24 to record data. After the optical disc 22 is put on the loader 14, the motor 12 will drive the loader 14 and the tracks 24 on the optical disc 22 will rotate across a pick-up head 16. Using the pick-up head 16, the control circuit 18 can access the data on the tracks 24. The control circuit 18 is controlled by a host 26 to access data on the optical disc 22. The host 26 can be a computer system such as PC.
To make the recording of data onto the optical disc 22 more reliable, there is a certain defect management mechanism in more advanced optical disc specifications. One of the most common ways is to allocate a portion of the optical disc 22 as a spare recording area. Whenever there are defects on an optical disc that make recording impossible, the data that is supposed to be recorded in the defective area will then be recorded in the spare recording area instead. Thus, the defects will not affect the recording of data on the optical disc 22.
Please refer to FIG. 2. FIG. 2 shows the allocation of spare recording areas and normal recording areas under the specification of CD-MRW(Compact Disc-Mount Rainier reWritable). As shown in FIG. 2, the track 24 that is used for data recording is divided into several major areas. These areas include a Lead-In Area (LI), a Program Area (PA), and a Lead-Out Area (LO). The LI and the LO are used respectively for marking the beginning and the end of the tracks 24. The LI comprises one area as a Main Table Area (MTA) to store a Defect Table (DT). The PA is used to record data. The PA is divided into a pre-gap (P0), a General Application Area (GAA), a Secondary Table Area (STA) to store a backup copy of the defect table DT, a plurality of Data Areas (DA), and a plurality of Spare Areas (SA).
In FIG. 2, different Data Areas (DA) are marked as DA(1), DA(2), . . . all the way to DA (N). There is also a plurality of Spare Areas (SA) in the PA to match the DA, different SA are marked with SA(1), SA(2), . . . to SA(N) respectively. Every DA has a plurality of Data Packet Areas (Pd). Every Pd has a plurality of user data blocks (Bd). Every Bd is used to record one block of data. Similarly, every SA(n) is further divided into a plurality of Spare Packet Areas (Ps). Every Ps comprises a plurality of spare data blocks (Bs). To facilitate discussion later on, there are three data blocks specifically marked Bd1, Bd2, and Bd3 and another three spare blocks specifically marked Bs1, Bs2, and Bs3 shown in FIG. 2. Whether it is the data block Bd or spare the block Bs, they are all writable data blocks with the same data storage capacity. For instance, in the specification of CD-MRW, every data area DA generally has 136 Pd and every packet Pd has 32 user data blocks Bd, every spare area SA has 8 packets Ps and every packet Ps has 32 spare blocks Bs. Every user data block Bd and spare area Bs contains room for 2 k bytes of data respectively.
In order to manage these data blocks Bd and spare blocks Bs, every data block Bd and spare block Bs has its own address (i.e. PBN, Physical Block Number). On the track 24, the address of each data block Bd and spare block Bs is unique. The value of each address corresponds to the physical order of the Bd, Bs on the track 24. An arrow A1 in the FIG. 2 points from the left to the right, the data area Bd on the left hand side has smaller address value. For example, in FIG. 2, the address value of the data area Bd is smaller than the address value of the data area Bd2 and the address value of data area Bd2 is smaller than that of Bd3, etc. The address value of every data block Bd in the data area DA(1) is smaller than the address value of a data block Bd in the data area DA(2), etc. Similarly, the address value of a spare block Bs1 is smaller than that of Bs2 and the address value of spare block Bs2 is smaller than that of Bs3. The address value of every spare block Bs in the spare area SA(1) is smaller than the address value of every spare block in the spare area SA(2).
We can describe the basic principle of the optical disc 22 defect management as follows. Whenever the optical disc drive 10 needs to write data from the host 26 (refer to FIG. 1) to the optical disc 22, the optical disc drive 10 will first write data onto a data block Bd(i) of the track 24. If the optical disc drive 10 encounters a defect and can not record data to the data block Bd(i) correctly, the optical disc drive 10 will find a substitute spare block Bs and write the data that was meant to be in this defective data block Bd(i)into the substitute spare block Bs.
In practice, the address of every defective data block Bd, the address of the substituted spare block Bs, and a mapping indicating the relationship is recorded in the defect table DT of the optical disc 22. When the optical disc drive 10 wants to read from the optical disc 22 and reaches the defective data block Bd, it locates the corresponding substituted spare block Bs via a record in the defect table DT, and reads the data on this substituted spare block Bs. According to the operational principle described above, even with some defects on the optical disc 22(caused by scratches or microdust), by setting up and using spare blocks Bs to implement defect management via the defect table DT, data can still be recorded on the optical disc 22.
As described above, the defect table DT records the usage status of each spare block Bs. Please refer to FIG. 3. FIG. 3 is a sketch map of the main data structure of the defect table DT in FIG. 2. The defect table DT has a plurality of Defect Table Blocks (DTB) (different Defect Table Blocks are marked DTB(1), DTB(2) . . . respectively). Each DTB has a plurality of entries 28. A plurality of DTB can be collected to form one defect table packet, so the DTB in the defect table DT can be divided into a plurality of defect table packets.
The total number of DTB in the defect table DT is the same as the number of spare areas SA in the track 24. The number of entries 28 in each DTB is the same as the number of the allocated spare blocks Bs in the spare area SA. In other words, every entry 28 in the defect table DT maps to one spare block Bs and records the usage status of this spare block Bs. Basically, each DTB maps to one spare area SA and every entry 28 of DTB is used to record the usage status of one spare block Bs in the corresponding spare area SA. However, in some special cases, there will be some entries 28 in the DTB that record a spare block Bs usage status of another spare area SA.
Please refer to FIG. 4A. FIG. 4A is a detailed sketch map of the data structure of the defect table DT. As shown in FIG. 4A, the spare area SA(n−1) on the track 24 contains spare block SO. The spare area SA(n) has spare blocks S1 through S16. The data area DA(n−1) includes data blocks Dx through Dy. The data area DA(n) includes data blocks D1 through D7. In the defect table DT, the data block DTB(n−1) is mainly used to record the usage status of corresponding spare blocks in the spare area SA(n−1). In every entry 28 that maps to one spare block Bs records one status information 29A, one spare block Bs address information 29B, and one data block Bd address information 29C. The spare block Bs address information 29B records the spare block Bs address mapped to this entry. To facilitate further discussion, three entries are marked 28A, 28B, and 28C respectively in FIG. 4A.
For each spare block Bs on the track 24, there are three different possibilities. First, a spare block Bs is already used to substitute for a defective data block Bd and contains the data that was supposed to be written onto this defective data block Bd. Second, although the spare block Bs can record data normally, it is not yet used to substitute for a defective data block Bd. Third, the spare block is defective and cannot be used to record any data.
For example, in FIG. 4A, the spare block S0 of the spare packet SA(n−1) and the spare blocks S1, S2,S3,S5,S6,S8,S10, and S11 of the spare packet SA(n) are used as substitutes to record data originally meant for specific defective data blocks Bd. The entries 28 that were used to record the usage status of these spare blocks Bs can also be called “used entries”. The spare blocks Bs that these entries map to were used to substitute for the defective data blocks Bd.
For instance, an entry 28A is used to record the usage status 29A of the spare block S5 and the address information 29B of the spare block S5. If the spare block S5 is used to substitute for a defective data block D3 for data recording, then the data block address information 29C of the entry 28A will record the address of the data block D3. Finally, the status information 29A is used to mark the entry 28A as a used entry. In FIG. 4A, a “U” is used to mark a used entry 28. In practice, the status information 29A is a 4 bit data. Similarly, the correspondences of the spare blocks S2, S0, S1, S6, S5, and S3 that are used to substitute for defective data blocks Dx, Dy (which reside in the data area DA(n−1)), D1, D2, D3, and D7 respectively, are each mapped in used entries 28A. All of the used entries 28A are gathered together and form a group in the record block DTB(n) as shown on FIG. 4A.
When the optical disc drive 10 tries to access data in a defective data block Bd on the optical disc 22, the optical disc drive 10 uses the address of this defective data block Bd to find the corresponding entry 28A that records the address 29C of this defect data block Bd. The optical disc drive 10 then uses the address 29B of the corresponding spare block Bs via this entry to use this spare block Bs to substitute for the original defective data block Bd for data accessing.
The spare blocks S13, S14 to S15, and S16 in FIG. 4A are all normal recordable spare blocks Bs, but they are not yet used to substitute for a defective data block Bd. The entries 28B recording the usage status 29A of these spare blocks Bs are called “free entries”. For instance, the entry 28B of the spare block S15 is a free entry. The spare block address information 29B of the entry 28B will record the address of the spare block S15. Because the spare block Bs that maps to a free entry is not yet used to substitute for a defective data block Bd, the data block address information 29C will not record the address of a specific data block Bd. In FIG. 4A, the status information 29A is marked with an “F” to indicate that the entry 28B is a free entry. Based on the same reasoning, the status information 29A of the spare blocks S13, S14, and S16 are also marked with an “F” in the respective entries 28B. Similar to the allocation of used entries, in a record block DTB(n), all of the recordable free entries are also gathered together to form a group, as shown in FIG. 4A.
Just like the data blocks Bd can be damaged and become defective data blocks Bd, the spare blocks Bs in the spare area SA can also be damaged and become defective spare blocks Bs. For instance, in FIG. 4A, spare blocks S4, S7, S9, and S12 are defective spare blocks. Entries 28C that are used to record the usage status 29A of the spare blocks S4, S7, S9, and S12 are called unusable entries. For example, the address of the defective spare block S4 is recorded in the spare block address information 29B of the unusable entry 28C. The defective spare block S4 cannot be used to substitute for any defective data block Bd for data recording, so the data block address information 29C of the data entry 28C will not record an address of any specific data block Bd. In FIG. 4A, the status information 29A is marked “D” to indicate that the entry 28C is an unusable entry. Similarly, the defective spare blocks S7, S9, and S12 are also recorded as unusable entries. For the same record block DTB, all of the unusable entries 28C are also gathered together to form a group as shown in FIG. 4A.
From the description above, the usage status 29A of any spare block Bs is known based on the possible three entries (used, free, and unusable). In order to streamline the process of defect management, the entries of the record block DTB in the defect table DT are sorted. As described above, the data blocks Bd and the spare blocks Bs all have addresses. Every used entry 28 in the defect table is sorted into ascending order by the address of the defective block 29C.
Take FIG. 4A as an example, the defective data blocks Bd from left to right are Dx, Dy, D1, D2, and D3 to D7. The data block Dx has the lowest address value, and from left to right the value increases (Dx<Dy<D1<D2< . . . <D7)with the data block D7 having the highest address value. The used entries 28A that record the addresses of these defective data blocks are also sorted by the address value order of defective data blocks Bd. As shown in FIG. 4A, in a data block DTB(n), among all the used entries 28A, the used entry 28A that records the address of the data block Dy is arranged at the left hand side of the diagram, and the order of the used entries 28A is according to the order of the addresses of the data blocks Dy, D1, D2, and D3 to D7. In practice, all the used entries 28A in the record block DTB of the defect table DT will follow the magnitude order of the defective data block address. In other words, in the record block DTB(n−1), of all the defective data block addresses recorded by the used entries 28A, the highest address is the rightmost address. In the record block DTB(n), every defective data block address recorded by the used entries 28A will be higher than the rightmost address in the record block DTB(n−1).
Compared to the order arrangement of the used entries 28A in the defect table DT, the order the free entries 28B is based on the spare block Bs addresses that the free entries 28B record. In FIG. 4A, the spare blocks Bs from left to right are S1, S2, S3 through S14, S15, and S16. The spare block S1 has the lowest address value, and from left to right the value of each address increases (S1<S2<S3< . . . <S14<S15<S16) with the spare block S16 having the highest address value. For the spare blocks S13, S14, S15, and S16 that are not used to substitute for defective data blocks Bd, the corresponding free entries 28B also follow the same order from left to right as shown in FIG. 4A. Unusable entries 28c do not require any special sorting.
When the optical disc drive 10 accesses the data block Bd in the data area DA(n) sequentially, the optical disc drive 10 encounters the defective data blocks D1, D2 and D3. If the data area DA(n)is arranged according to the address of the defective data block Bd sequence and used entries 28A are sorted as a group, the optical disc drive can retrieve the address of the substituted spare block Bs via the used entry 28A. Based on the address sequence to arrange the spare blocks Bs and the gathering of the free entries 28A, the optical disc drive 10 can find free spare blocks 28B to substitute for the defective data blocks Bd.
However, because these three types of entries (used, free, and defective) are gathered to form groups and sorted differently according to their types, the number and position of all the entries 28 in the defect table DT will change with repeated data accessing. Please refer to FIG. 4B (and also FIG. 4A). FIG. 4B shows, if the optical disc 22 status changes, how the defect table from FIG. 4A is affected. Suppose during the operation of data writing, the optical disc drive 10 finds a normal data block B8 on track 24 has become defective (in other words, the data block B8 is normal in FIG. 4A but is defect in FIG. 4B). The optical disc drive 10 can no longer write data to the data block B8. Following the defect management principles mentioned earlier, the optical disc drive 10 searches for a free entry 28B in the defect table DT to find a free spare block 28A (not used as a substituted block for any defective data block)and locates the spare block S13. Then the spare block S13 is used to substitute for the defect data block D8.
After the usage status 29A of the free entry 28B for the spare block S13 is changed from “free” to “used”, the free entry 28B that records the address of the spare block S13 in the record block DTB(n) will be a used entry. The changed status information 29A from an “F” to a “U” makes the free entry 28B become a “New” used entry 28A. Of course, now there is one less free entry in FIG. 4B than in FIG. 4A.
As described above, the used entries 28A need to be sorted. Because the address value of the data block B8 is somewhere between the defective data blocks D1 and D2 the “New” used entry 28A has to be put in between the two used entries 28A that record the defective blocks D1 and D2. From this example it can be seen that the order of the used entries 28A after sorting may be different from the corresponding spare block Bs sequence arranged on the track 24.
Furthermore, as shown by FIGS. 4A and 4B, if there are more defective data blocks Bd in the data area DA(n−1) than the normal spare blocks Bs in the spare area SA(n−1), the spare blocks Bs in the spare area SA(n) are used. When the used entries 28A are sorted according to the defective data block Bd addresses, the used entry 28A that records the spare block S2 originally in the spare are SA(n) might be placed in the record block DTB(n−1) that normally maps to the spare area SA(n−1). Similarly, for the spare block S0 that belongs to the spare area SA(n−1), the used entry 28A might be moved to the record block DTB(n). In response to the “New” used entry 28A, the defect table DT with changed content will be rewritten onto the optical disc 22. Afterwards, when the optical disc 10 is accessing data and encounters the defective data block B8, from the updated defect table DT it can locate the corresponding spare block S13.
From the discussion above, after repeated data accessing, the optical disc 22 will eventually have defects. The entry number and sequence of the defect table DT will keep changing too. Because the used entries 28A and the free entries 28B are grouped and sorted within their respective groups, the entries 28 used to record the usage status 29A of the spare blocks Bs can no longer be arranged sequentially according to the spare blocks Bs sequence on the track 24. For instance, as mentioned in FIGS. 4A, 4B, even with the spare blocks S12, S13, and S14 on neighboring positions on track 24, the entries 28 used to record the usage status 29A of the spare blocks S12, S13, and S14 will not lineup in neighboring positions and follow the sequence of the spare blocks S12, S13 and S14.
Even within the used entries 28A of every record block DTB, the spare blocks Bs with neighboring entry 28 records are not necessary the neighboring spare blocks Bs on the track 24. In other words, the defect table DT based on the spare block usage status 29A cannot reflect the actual sequence of the spare blocks Bs on the track 24.
If the address of the spare block Bs is needed to refer to the usage status 29A of this spare block Bs, the spare block Bs address information 29B of each spare block Bs in the defect table DT must be checked one by one to retrieve the status of this spare block Bs via the status information 29A from the entry 28. For instance, if the optical disc drive 10 encounters one defective spare block Bs in some spare area SA during optical disc 22 data accessing, the spare block Bs address information 29B of all the unusable entries 28C is checked one by one to find out if this spare block Bs is already recorded in the defect table DT as a defective spare block Bs. If this spare block Bs is not recorded as a defective spare block Bs yet, this spare block Bs might be recorded as a spare block Bs in a free entry 28B. Now the usage status 29A of the entry 28B must be changed accordingly. Because there is no way to directly retrieve the usage status 29A of the spare block Bs simply by address, the process of defect management is cumbersome and slow.